Image halftoning is a process to convert a continuous tone image into a binary or “halftone” image with only black and white dots, which resembles the original image when viewed from a distance. Inverse halftoning is the process to estimate the original image from the halftone image.
One simple method for inverse halftoning is simple lowpass filtering, but low pass filtering tends to give blurred images. Other, more sophisticated methods include set-theoretic projection-onto-convex-set (POCS) methods (see N. T. Thao, “Set Theoretic Inverse Halftoning”, Proc. of IEEE Int. Conf. On Image Processing, Vol. 1, pp 783-6, October 1997), wavelet-based methods using edge information in highpass wavelet images (Z. Xiong, M. T. Orchard, K. Ramchandran, “Inverse Halftoning using Wavelets”, Proc. of IEEE Int. Conf. On Image Processing, Vol. 1, pp 569-72, Sept. 1996), adaptive inverse halftoning using least mean square sliding window filter and Wiener filter postprocessing (L. M. Chen, H. M. Hang, “An adaptive Inversee Halftoning Algorithm”, IEEE Trans. Of Image Processing, Vol. 6, No. 8, pp 1202-9, August 1997), a MMSE and MAP projection-based method (C. M. Miceli, K. J. Parker, “Inverse halftoning”, J. of Electronic Imaging, Vol. 1, No. 2, pp 143-51, Apr. 1992.) and a three-level cascade algorithm (P. W. Wong, “Inverse halftoning and Kernel Estimation for Error Diffusion”, IEEE Tran. On Image Processing, Vol. 4, No. 4, pp 486-98, April 1995).
These methods can usually give acceptable visual quality of estimated images (for example, they can produce an image with continuous pixel values which does not suffer excessive blurring), but they are computationally expensive.
U.S. Pat. No. 5,243,444 proposes a computationally simpler “Sigma” algorithm. In each iteration a value of a parameter sigma is defined, as is a neighborhood of each pixel. The value of the image at each given pixel is then reset as an average (that is a simple sum, not a weighted sum) of the image values of those pixels in the neighborhood of the given pixel which have a value within sigma of the value at the given pixel. In successive iterations the neighborhoods become larger and the value of sigma becomes smaller.